|
In computer science, X + Y sorting is the problem of sorting pairs of numbers by their sum. Given two finite sets and , the problem is to order all pairs in the Cartesian product by the key . The problem is attributed to Elwyn Berlekamp. This problem can be solved using a straightforward comparison sort on the Cartesian product, taking time for sets of sizes and . When it is assumed that , the complexity is , which is also the best known bound on the problem, but whether X + Y sorting can be done strictly faster than sorting arbitrary numbers is an open problem.〔 The number of required comparisons is certainly lower than for ordinary comparison sorting: Fredman showed, in 1976, that X + Y sorting can be done using only comparisons, though he did not show an algorithm. The first actual algorithm that achieves this number of comparisons and total complexity was only published sixteen years later. On a RAM machine with word size and integer inputs , the problem can be solved in operations by means of the fast Fourier transform. Skiena recounts a practical application in transit fare minimisation, an instance of the shortest path problem: given fares and for trips from departure A to some intermediate destination B and from B to final destination C, determine the least expensive combined trip from A to C. ==See also== * 3SUM * Integer sorting 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「X + Y sorting」の詳細全文を読む スポンサード リンク
|